import java.util.Random;

//排序数组 （数组分三块实现）
//测试链接 https://leetcode.cn/problems/sort-an-array/description/
public class SortArray {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);

        return nums;
    }

    public void quickSort(int nums[], int l, int r){
        if(l >= r){  //递归出口
            return;
        }
        int key = nums[new Random().nextInt(r - l + 1) + l]; //随机从数组中获取一个基准值
        int left = l - 1, right = r + 1, i = l;

        //分成三块
        while(i < right){
            if(nums[i] == key) {
                i++;
            }else if(nums[i] < key){
                swap(nums, ++left, i++);
            }else {
                swap(nums,--right, i);
            }
        }
        //分完结果:
        //[l,left]          < key
        //[left+1,right-1]  = key
        //[right, r]        > key

        quickSort(nums,l,left);  //排序坐部分
        quickSort(nums,right,r); //排序右部分
    }

    public void swap(int nums[], int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
